import { ProductTree } from "@/api/interface";

/**
 * 计算节点坐标，避免节点重叠
 * @param edges 边 用于计算节点坐标
 * @param rootId 根节点id（-1）
 * @param spacingX x轴各个节点间距
 * @param spacingY y轴各个节点间距
 * @returns 节点坐标{index:number ,x:number, y:number}
 */
const calculateNodeCoordinates = (edges: ProductTree.Edge[], rootId: number, spacingX: number, spacingY: number) => {
  const nodeCoordinates: ProductTree.NodeLocation[] = [];
  const childrenMap = new Map<number, number[]>();
  // 用于跟踪所有出现的节点ID
  const allNodeIds = new Set<number>();
  // 记录每个节点的引用关系：[sourceId, targetId] 数组
  const nodeReferences = new Map<number, number[][]>();
  // 用于跟踪已占用的位置
  const occupiedPositions = new Map<string, boolean>();

  // 构建子节点映射和引用关系
  edges.forEach(edge => {
    // 构建子节点映射
    if (!childrenMap.has(edge.source)) {
      childrenMap.set(edge.source, []);
    }
    childrenMap.get(edge.source)!.push(edge.target);

    // 记录所有节点ID
    allNodeIds.add(edge.source);
    allNodeIds.add(edge.target);

    // 记录引用关系
    if (!nodeReferences.has(edge.target)) {
      nodeReferences.set(edge.target, []);
    }
    nodeReferences.get(edge.target)!.push([edge.source, edge.target]);
  });

  // 计算每个节点有多少个引用
  const referenceCount = new Map<number, number>();
  for (const [nodeId, references] of nodeReferences.entries()) {
    referenceCount.set(nodeId, references.length);
  }

  const processedReferences = new Map<number, number>();
  // 用于跟踪已添加到结果中的基本节点ID (不包括重复实例)
  const addedBaseNodes = new Set<number>();

  // 计算子树大小 (包括当前节点在内的总节点数)
  const getSubtreeSize = (nodeId: number, visited = new Set<number>()): number => {
    if (visited.has(nodeId)) return 0;
    visited.add(nodeId);

    const children = childrenMap.get(nodeId) || [];
    let size = 1; // 当前节点

    for (const child of children) {
      size += getSubtreeSize(child, new Set([...visited]));
    }

    return size;
  };

  // 检查位置是否已被占用
  const isPositionOccupied = (x: number, y: number): boolean => {
    return occupiedPositions.has(`${Math.round(x)},${Math.round(y)}`);
  };

  // 标记位置为已占用
  const markPositionAsOccupied = (x: number, y: number): void => {
    occupiedPositions.set(`${Math.round(x)},${Math.round(y)}`, true);
  };

  // 寻找可用位置 - 如果当前位置被占用，找附近可用位置
  const findAvailablePosition = (baseX: number, baseY: number): { x: number; y: number } => {
    // 如果基础位置可用，直接使用
    if (!isPositionOccupied(baseX, baseY)) {
      return { x: baseX, y: baseY };
    }

    // 否则，螺旋式地搜索可用位置
    let distance = 1;
    const maxAttempts = 20; // 防止无限循环

    while (distance <= maxAttempts) {
      // 检查水平方向
      for (let dx = -distance; dx <= distance; dx += 2) {
        const newX = baseX + (dx * spacingX) / 4;
        if (!isPositionOccupied(newX, baseY)) {
          return { x: newX, y: baseY };
        }
      }

      // 检查垂直方向
      for (let dy = -distance; dy <= distance; dy += 2) {
        const newY = baseY + (dy * spacingY) / 4;
        if (!isPositionOccupied(baseX, newY)) {
          return { x: baseX, y: newY };
        }
      }

      // 增加搜索范围
      distance++;
    }

    // 如果附近没找到可用位置，尝试一个完全不同的位置
    return { x: baseX + spacingX, y: baseY + distance * spacingY };
  };

  // 递归定位节点
  const positionNode = (nodeId: number, x: number, y: number, parentId?: number) => {
    let instanceOffset = 0;

    // 如果是多个引用的目标节点，需要跟踪当前处理的是第几个引用
    if (referenceCount.get(nodeId) && referenceCount.get(nodeId)! > 1) {
      if (!processedReferences.has(nodeId)) {
        processedReferences.set(nodeId, 0);
      } else if (parentId) {
        // 针对特定的父-子关系，计算实例编号
        const referenceIdx = nodeReferences.get(nodeId)!.findIndex(ref => ref[0] === parentId && ref[1] === nodeId);
        if (referenceIdx !== -1) {
          instanceOffset = referenceIdx;
          processedReferences.set(nodeId, processedReferences.get(nodeId)! + 1);
        }
      }
    }

    // 为具有多个引用的节点添加Y轴偏移
    const instanceY = y + instanceOffset * (spacingY / 2);

    // 找到一个可用位置
    const { x: finalX, y: finalY } = findAvailablePosition(x, instanceY);

    // 标记位置为已占用
    markPositionAsOccupied(finalX, finalY);

    // 添加节点到结果
    nodeCoordinates.push({
      index: nodeId,
      x: finalX,
      y: finalY
    });

    // 标记基础节点已添加
    addedBaseNodes.add(nodeId);

    // 处理子节点
    const children = childrenMap.get(nodeId) || [];
    if (children.length === 0) return;

    // 子节点的X位置
    const childX = finalX + spacingX;

    // 计算子树的总大小，以便合理分配空间
    const totalSize = children.reduce((sum, childId) => sum + getSubtreeSize(childId, new Set()), 0);

    // 计算起始Y位置，让子树整体居中
    let childY = finalY - ((totalSize - 1) * spacingY) / 2;

    // 为每个子节点分配位置
    for (const childId of children) {
      const subtreeSize = getSubtreeSize(childId, new Set());

      // 调整子节点Y位置，考虑子树大小
      const centerY = childY + ((subtreeSize - 1) * spacingY) / 2;

      // 如果是第一次遇到这个子节点，或是作为不同父节点的重复引用时
      if (!addedBaseNodes.has(childId) || (referenceCount.get(childId) && referenceCount.get(childId)! > 1)) {
        positionNode(childId, childX, centerY, nodeId);
      }

      // 更新下一个子节点的Y位置，考虑当前子树大小
      childY += subtreeSize * spacingY;
    }
  };

  // 从根节点开始布局
  positionNode(rootId, 0, 0);

  // 处理孤立节点（没有连接到根节点的节点）
  allNodeIds.forEach(nodeId => {
    if (!addedBaseNodes.has(nodeId)) {
      const lastY = nodeCoordinates.length > 0 ? Math.max(...nodeCoordinates.map(coord => coord.y)) + spacingY * 1.5 : spacingY;
      positionNode(nodeId, 0, lastY);
    }
  });

  return nodeCoordinates;
};

function assignNodeIndices(edges: ProductTree.Edge[]) {
  // 收集所有唯一节点ID
  const allNodeIds = new Set<number>();

  // 记录节点作为目标节点出现的次数
  const targetOccurrences = new Map<number, number>();
  // 将所有节点ID添加到集合中
  edges.forEach(edge => {
    allNodeIds.add(edge.source);
    allNodeIds.add(edge.target);

    // 统计目标节点出现次数
    if (!targetOccurrences.has(edge.target)) {
      targetOccurrences.set(edge.target, 1);
    } else {
      targetOccurrences.set(edge.target, targetOccurrences.get(edge.target)! + 1);
    }
  });

  // 为每个唯一节点分配一个从1开始的索引
  let nextIndex = 1;
  // 保留nodeToIndexMap用于内部计算，但不在返回值中包含它
  const nodeToIndexMap = new Map<number, number[]>();
  const indexToNodeMap = new Map<number, number>();
  // 首先为非重复目标节点分配索引
  allNodeIds.forEach(nodeId => {
    if (!targetOccurrences.has(nodeId) || targetOccurrences.get(nodeId) === 1) {
      // 如果节点不是目标节点或只作为目标出现一次，分配一个索引
      nodeToIndexMap.set(nodeId, [nextIndex]);
      indexToNodeMap.set(nextIndex, nodeId);
      nextIndex++;
    }
  });

  // 然后为重复目标节点分配多个索引
  allNodeIds.forEach(nodeId => {
    if (targetOccurrences.get(nodeId) && targetOccurrences.get(nodeId)! > 1) {
      const occurrences = targetOccurrences.get(nodeId)!;
      const indices: number[] = [];

      for (let i = 0; i < occurrences; i++) {
        indices.push(nextIndex);
        indexToNodeMap.set(nextIndex, nodeId);
        nextIndex++;
      }

      nodeToIndexMap.set(nodeId, indices);
    }
  });

  // 跟踪每个目标节点已使用的索引位置
  const usedIndicesCount = new Map<number, number>();

  // 创建带有索引的边集合
  const indexedEdges = edges.map(edge => {
    const sourceIndex = nodeToIndexMap.get(edge.source)![0];

    let targetIndex: number;
    if (targetOccurrences.get(edge.target)! > 1) {
      // 如果目标节点有多个实例，分配下一个可用索引
      if (!usedIndicesCount.has(edge.target)) {
        usedIndicesCount.set(edge.target, 0);
      } else {
        usedIndicesCount.set(edge.target, usedIndicesCount.get(edge.target)! + 1);
      }
      const instanceIdx = usedIndicesCount.get(edge.target)!;
      targetIndex = nodeToIndexMap.get(edge.target)![instanceIdx];
    } else {
      // 目标节点只有一个实例
      targetIndex = nodeToIndexMap.get(edge.target)![0];
    }

    return {
      source: sourceIndex,
      target: targetIndex
    };
  });

  return {
    // 索引到节点ID的映射
    indexToNodeMap,
    // 带有索引的边集合
    indexedEdges
  };
}
export { calculateNodeCoordinates, assignNodeIndices };
